home *** CD-ROM | disk | FTP | other *** search
/ Libris Britannia 4 / science library(b).zip / science library(b) / PACKET / BSQ.ZIP / BSQ.C < prev    next >
C/C++ Source or Header  |  1986-02-24  |  25KB  |  856 lines
  1. /************************************************************************
  2.  * Binary file squeeze for packet transmission    Steve Ward W1GOH 1/86    *
  3.  * Version 2.0 2/20/86                            *
  4.  ************************************************************************
  5.  **  Copyright 1986 by W1GOH on bahalf of the Amateur Radio community. **
  6.  **   Unrestricted permission to use, copy, modify, extend, improve,   **
  7.  **          and build upon this program is hereby granted.           **
  8.  ************************************************************************
  9.  *                                    *
  10.  * Converts a binary file to ASCII, excluding "special" characters    *
  11.  *   which might cause trouble over ASCII transmission media (viz.    *
  12.  *   packet radio).  Does some data compression.            *
  13.  *                                    *
  14.  * USAGE:                                *
  15.  *   bsq <options> file.ext [outname]                    *
  16.  *    reads binary file.ext, writes file.bsq (or outname if specified)*
  17.  *   bsq <options> file.bsq [outname]                    *
  18.  *      reads file.bsq, writes original file name (or outname)        *
  19.  *                                    *
  20.  *   <options> may include:                        *
  21.  *    -b    Bootstrap mode.  Does simple bit-stuffing, no data    *
  22.  *        compression.  Output file suitable for simple BASIC pgm    *
  23.  *    -o    Old format.  Writes a .BSQ file compatible with earlier    *
  24.  *        versions of BSQ.                    *
  25.  *                                    *
  26.  *  A trivial BASIC program suffices to decode files converted with    *
  27.  *    the -b option.  Although originally intended for bootstraping    *
  28.  *    the BSQ program over the air, it may be used routinely if     *
  29.  *    expedient.  However, the BASIC pgm is very primitive indeed.    *
  30.  *                                    *
  31.  *  This program is written in vanilla C, and should be easy to port.    *
  32.  *     Currently I have it running on VAX/UNIX and IBM PCs; I         *
  33.  *    encourage interested parties to port it to CPM and other    *
  34.  *    environments.                            *
  35.  *                                    *
  36.  ************************************************************************
  37.  *                                    *
  38.  * The encoding algorithm involves the following techniques:        *
  39.  *   (1) Basic bit-stuffing, breaking input stream of 8-bit binary bytes*
  40.  *       into an output stream of 6-bit printable ASCII chars.  Each    *
  41.  *     of the latter is relocated to printable range by adding 33 dec.*
  42.  *   (2) Data compression, which uses 28 of the remaining 30 printable    *
  43.  *     ASCII codes as "meta" characters abbreviating input byte     *
  44.  *     sequences.  My compression scheme is adapted from the TERSE    *
  45.  *     algorithm; it involves 2 identical FSMs (at sender & receiver,    *
  46.  *     respectively) which cause meta chars to be defined in identical*
  47.  *     way at both ends on basis of communications history.  In     *
  48.  *     particular, each output step -- either of a bit-stuffed byte    *
  49.  *     or of a meta symbol -- causes a new meta symbol to be defined    *
  50.  *     as the PREVIOUS TWO output symbols.  The metasymbol to be    *
  51.  *     thus defined is selected via a deterministic LRU approximation,*
  52.  *     avoiding conflicts with active subnodes via a reference count.    *
  53.  *   (3) A 29th character serves as a REPEAT code.  REPEAT followed by    *
  54.  *     a 6-bit count (relocated to ASCII per above) causes the last    *
  55.  *     INPUT symbol to be rescanned <count> times... thus if the    *
  56.  *     last input symbol was a meta symbol representing a 100-byte    *
  57.  *     string, the repeat sequence might expand to 6300 bytes.    *
  58.  *   (4) Additional compression hacks are envisioned for the remaining    *
  59.  *     character.  Watch this space.                    *
  60.  *                                    *
  61.  * The bit-stuffing yields an output file 4/3 the size of the input,    *
  62.  * inflated further by (1) a header line and (2) CR/LFs at each output    *
  63.  * line.                                *
  64.  *                                    *
  65.  * BUGS:                                *
  66.  *   1. The program has suffered from a period of evolution, and needs    *
  67.  *    to be cleaned up somewhat.  Volunteers welcome.            *
  68.  *   2. The algorithm is still the subject of sporadic hacking.  It    *
  69.  *    might change incompatibly, if I hit upon something significantly*
  70.  *    better.  Incompatibities are in theory detectable, however,    *
  71.  *    by virtue of a version number in .bsq file headers.        *
  72.  ************************************************************************
  73.  * Program history:                            *
  74.  *  12/24/85 SAW: First version working.                *
  75.  *   1/1/86  SAW: Added data compression (v. 1.0)            *
  76.  *   2/17/86 SAW: Cleaned up, implemented K1OJH's suggestion of output    *
  77.  *    to file named in header.  Also part number, nparts in header.    *
  78.  *    (v. 1.2)                            *
  79.  *   2/20/86 SAW: Improved data compression, by avoiding flushing the    *
  80.  *    bit-stuff pipeline on meta chars (uses buffer BinBuf for latter)*
  81.  *    Also "suspicious text" messages. (v. 2.0)            *
  82.  ************************************************************************/
  83.  
  84. #include <stdio.h>
  85. #define VERSION    2        /* Version number, for file header    */
  86. char *ANode();            /* Here for debugging only!        */
  87.  
  88. /************************************************************************
  89.  * POTENTIAL MACHINE/COMPILER DEPENDANCIES                *
  90.  ************************************************************************/
  91. typedef unsigned char byte;
  92. typedef unsigned short ushort;
  93.  
  94. /************************************************************************
  95.  * Parameters & Globals                            *
  96.  ************************************************************************/
  97.  
  98. #define    NTS    28        /* Number of definable nonterminals    */
  99. #define    NNODES    NTS        /* Max nodes for data compression    */
  100.  
  101. #define    ASCBITS 6        /* Bits per ASCII character.        */
  102. #define    ASCODES (1<<ASCBITS)    /* number of codes for bitstuffing    */
  103. #define    ASCBAS  041        /* Base char for code.            */
  104. #define    METABAS    (ASCBAS+ASCODES)/* Base code for meta chars        */
  105. #define    METARPT    (METABAS+NTS)    /* Repeat code.                */
  106.  
  107. int NNodes = NNODES;        /* Number of nodes used            */
  108. char *from, to[100];        /* Source, destination file names    */
  109. char fname[100];        /* Name from .bsq file            */
  110. FILE *in, *out;            /* Input, output streams.        */
  111.  
  112. char    BFlag=0;        /* Bootstrap- mode            */
  113. char    OldFlag=0;        /* Old format.                */
  114.  
  115. typedef ushort NodeID;        /* Node identifier:            */
  116.  
  117. #define    ATOMIC(N) ((N)&0x8000)    /*  Atomic node... else internal.    */
  118. #define    DATA(N)     ((N)&0xFF)    /*  Data from atomic node.        */
  119. #define    UNUSED ((NodeID) 0xFFFF)/* Code for undefined node.        */
  120. #define    MKATOM(D) ((D)|0x8000)    /* Make an atomic node, given index.    */
  121.  
  122. struct Node
  123.  {    NodeID Left, Right;    /* Inferiors.                */
  124.     ushort Refs;        /* Reference count.            */
  125.     ushort Size;        /* Total number of terminals        */
  126.     ushort Next, Prev;    /* LRU Chain.                */
  127.     ushort Prefix;        /* List of nodes having this as Left    */
  128.     ushort Thread;        /* Above thread.            */
  129.  } Nodes[NNODES];        /* The node database.            */
  130.  
  131. NodeID    LRUHead;        /* Most recently used nonterminal.    */
  132. NodeID    Prefixes[256];        /* Prefix threads for terminals        */
  133.  
  134. #define NodeSize(N) ((ATOMIC(N)? 1:Nodes[N].Size))
  135.  
  136. #define    COLUMNS    72        /* Number of chars/output line        */
  137. int    CheckColumns=COLUMNS;    /* Number of chars/line expected on inp    */
  138. unsigned checksum;        /* Checksum of input bytes        */
  139. long     NBytes;        /* Bytes read/written            */
  140. long     Length;        /* Target length of file.        */
  141. NodeID Previous = UNUSED;        /* For state machine.        */
  142.  
  143. #define    BBSIZE    1024        /* Size of buffer for meta-chars --     */
  144. char BinBuf[BBSIZE];        /* Used to buffer meta-output whilst     */
  145. int BinN;            /*   holding partial bit-stuff word.    */
  146. int Partials = 1;        /* FLAG: nonzero iff saving partials.    */
  147.  
  148. #define OutBin(bb) BinBuf[BinN++] = bb    /* Output a byte to BinBuf    */
  149.  
  150.  
  151. NodeInit()
  152.  {    register i, j;
  153.  
  154.     for (i=0; i<256; i++) Prefixes[i] = UNUSED;
  155.  
  156.     for (i=0; i<NNodes; i++)    /* Fix up node pool        */
  157.      { Nodes[i].Left = UNUSED;    /* Free node.            */
  158.        Nodes[i].Refs = 0;        /* No references.        */
  159.        Nodes[i].Size = 0;
  160.        Nodes[i].Next = (i+1+NNodes)%NNodes;
  161.        Nodes[i].Prev = (i-1+NNodes)%NNodes;
  162.      }
  163.     LRUHead = 0;            /* Head of LRU chain.        */
  164.     Previous = UNUSED;
  165.  }
  166.  
  167. /* Allocate & return a node, bumping ref counts of inferiors.
  168.  * Finds least recently used node whose ref count is zero.
  169.  * Ref cnt of returned node is zero.
  170.  */
  171.  
  172. NodeID NewNode(left, right)
  173.  NodeID left, right;
  174.  {    register struct Node *p;
  175.     int n, oldn, oldnn = -1;
  176.  
  177.     /* Show left, right as used FIRST, to prevent re-allocating.    */
  178.     if (!ATOMIC(left)) Nodes[left].Refs++;
  179.     if (!ATOMIC(right)) Nodes[right].Refs++;
  180.  
  181.     /* Follow LRU chain, looking for candidate to recycle.        */
  182.     for (oldn = n = Nodes[LRUHead].Prev; ; n = p->Prev)
  183.      { if (n == oldnn) Error("Node alloc!");/* "Can't happen!"    */
  184.        oldnn = oldn;
  185.        p = &Nodes[n];
  186.        if (p->Refs == 0)        /* Unused node?            */
  187.         {    KillNode(n);        /* Yup, recycle it.        */
  188.         break;
  189.         }
  190.      }
  191.  
  192.     p->Left = left;
  193.     p->Right = right;
  194.     p->Refs = 0;            /* Presumably no superiors yet    */
  195.     p->Prefix = UNUSED;        /* No left superiors, yet    */
  196.     p->Size = NodeSize(left)+NodeSize(right);
  197.  
  198.     /* Splice onto proper Prefix thread:                */
  199.     if (ATOMIC(left))
  200.         { p->Thread = Prefixes[DATA(left)];
  201.           Prefixes[DATA(left)] = n;
  202.         }
  203.     else    { p->Thread = Nodes[left].Prefix;
  204.           Nodes[left].Prefix = n;
  205.           }
  206.  
  207.     Touch(n);            /* Bring it to head of LRU chn    */
  208.     return n;
  209.  }
  210.  
  211. /* De-allocate a node:
  212.  */
  213. KillNode(n)
  214.  {    register struct Node *p;
  215.     register NodeID *nid;
  216.  
  217.     p = &Nodes[n];
  218.     if (p->Left == UNUSED) return;        /* Unallocated node.    */
  219.  
  220.     /* Splice out of prefix list.                    */
  221.     if (ATOMIC(p->Left)) nid = &Prefixes[DATA(p->Left)];
  222.     else nid = &(Nodes[p->Left].Prefix);
  223.     for  (; *nid != UNUSED; nid = &(Nodes[*nid].Thread))
  224.      {    if (*nid == n)
  225.             { *nid = p->Thread;
  226.               break;
  227.             }
  228.      }
  229.  
  230.     /* Deref inferior nodes.                    */
  231.      if (!ATOMIC(p->Left)) Nodes[p->Left].Refs--;
  232.     if (!ATOMIC(p->Right)) Nodes[p->Right].Refs--;
  233.  
  234.     p->Left = p->Right = UNUSED;        /* Now nothings used.    */
  235.     p->Refs = 0;
  236.  }
  237.  
  238. /* "Touch" a nonterminal... ie, make it recent.
  239.  */
  240. Touch(n)
  241.  {    int prev, next;
  242.     register struct Node *p, *l;
  243.  
  244.     if (ATOMIC(n)) return;        /* Shouldnt happen, but ...    */
  245.  
  246.     p = &Nodes[n];            /* To become head of chain.    */
  247.     Nodes[p->Prev].Next = p->Next;    /* Splice out node n.        */
  248.     Nodes[p->Next].Prev = p->Prev;
  249.  
  250.     l = &Nodes[LRUHead];        /* Current head of chain.    */
  251.     p->Prev = l->Prev;        /* Splice in n as new head.    */
  252.     p->Next = LRUHead;
  253.     Nodes[p->Prev].Next = n;
  254.     l->Prev = n;
  255.     LRUHead = n;
  256.  }
  257.  
  258. /* Drive the database state: call whenever a node is output.        */
  259. NodeOut(n)
  260.  NodeID n;
  261.  {
  262.     if (Previous != UNUSED)        /* Define a new node.        */
  263.         { NodeID new;
  264.           new = NewNode(Previous, n);
  265.         }
  266.     Previous = n;
  267.  }
  268.  
  269. /* Lookahead Input routines:
  270.  */
  271.  
  272. byte ibuf[1024];            /* Lookahead buffer        */
  273. short ibufbase = 0,            /* Base index of buffer        */
  274.       ibufn = 0;            /* Bytes in buffer.        */
  275.  
  276. #define INEOF ((!ibufn)&&(feof(in)))    /* Detect EOF on input.        */
  277.  
  278. Peek(n)                    /* Returns -1 iff can't.    */
  279.  {    int nr;
  280.     register ch;
  281.  
  282.     while (ibufn <= n)
  283.      { if (n >= 1024) return -1;
  284.        if (feof(in)) return -1;    /* Can't read any more.        */
  285.        nr = (ibufbase+ibufn) & 1023;
  286.        while (!feof(in) && (ibufn < 1024))
  287.         { if ((ch = getc(in)) == EOF) break;
  288.           ibuf[nr++] = ch;
  289.           nr &= 1023;
  290.           ++ibufn;
  291.         }
  292.      }
  293.     return 0xFF & ibuf[(n+ibufbase) & 1023];
  294.  }
  295.  
  296. /* Remove next n input chars from buffer:                */
  297. Remove(n)
  298.  {    ibufbase = (ibufbase+n) & 1023;
  299.     ibufn -= n;
  300.  }
  301.  
  302.  
  303.  
  304.  
  305. NodeID    FindBest;
  306. int    FindSize;
  307.  
  308. /* Called with n=node, offset = next input symbol locn on match.
  309.  * Updates FindBest, FindSize to best (longest) match.
  310.  */
  311. MatchHit(n, offset)
  312.  {    NodeID thr;
  313.     register struct Node *p;
  314.  
  315.     p = &Nodes[n];
  316.     if (ATOMIC(n))
  317.      { if (!FindSize) { FindSize = 1; FindBest = n; }
  318.      }
  319.     else
  320.      { if (FindSize < p->Size) { FindSize = p->Size; FindBest = n; }
  321.        thr = p->Prefix;
  322.        FindRight(thr, offset);
  323.      }
  324.  
  325.  }
  326.  
  327. /* Follow a thread.  Find all matches of right inferior, calling MatchHit.
  328.  * Presumably, left nodes all match just fine.
  329.  */
  330.  
  331. FindRight(thr, offset)
  332.  {    register i;
  333.  
  334.     while (thr != UNUSED)
  335.      { if (i = AbMatch(offset, Nodes[thr].Right))
  336.         MatchHit(thr, offset+i);
  337.        thr = Nodes[thr].Thread;
  338.      }
  339.  }
  340.  
  341.  
  342. /* Find longest applicable abbreviation.
  343.  * Leaves Best node in FindBest, its size in FindSize;
  344.  * Returns size of best abbreviation, or 0 iff none.
  345.  */
  346.  
  347. NodeID    AbBest;            /* AbMatch return values: NodeID,    */
  348. int    AbSize;            /* Size of node.            */
  349.  
  350. Abbrev()
  351.  {    register i, j;
  352.  
  353.     if (((j = Peek(0)) == -1) ||        /* EOF.            */
  354.         ((i = Prefixes[j]) == UNUSED))    /* Nothing there.    */
  355.         return 0;            /* Return failure.    */
  356.  
  357.     FindBest = UNUSED;
  358.     FindSize = 0;
  359.     FindRight(i, 1);            /* Search for match.    */
  360.  
  361.     return FindSize;
  362.  }
  363.  
  364. /* Perform the recursive match.
  365.  * Returns results in AbBest, AbSize.
  366.  * Returns size, or 0 iff none.
  367.  * offset is position in input stream, n is node ID.
  368.  */
  369.  
  370. AbMatch(offset, n)
  371.  NodeID n;
  372.  {    register j;
  373.  
  374.     if (n == UNUSED) return 0;
  375.     if (ATOMIC(n))
  376.      { if (DATA(n) == Peek(offset))
  377.         { AbBest = n;
  378.           return AbSize = 1;
  379.         }
  380.        return 0;
  381.      }
  382.  
  383.     if (j = AbMatch(offset, Nodes[n].Left))
  384.      { register k;
  385.        if (k = AbMatch(offset+j, Nodes[n].Right))
  386.         { AbBest = n;
  387.           return (AbSize = j+k);
  388.         }
  389.      }
  390.     return 0;
  391.  }
  392.  
  393. /* Check for repeats.
  394.  * Returns size of repeat string (in bytes), or 0 iff none.
  395.  * Leaves repeat count in FindSize.
  396.  * Guarantees repeat count < 64.
  397.  */
  398. Repeat()
  399.  {    register size, i;
  400.  
  401.     if (Previous == UNUSED) return;
  402.     if (ATOMIC(Previous))        /* String of atoms?        */
  403.      { for (i=DATA(Previous), size=0; Peek(size) == i; size++)
  404.         if (size >= 63) break;
  405.        return FindSize=size;
  406.      }
  407.     FindSize = 0;
  408.  
  409.     for (size=0; i = AbMatch(size, Previous);)
  410.      { size += i;
  411.        if (++FindSize >= 63) break;
  412.      }
  413.     return size;
  414.  }
  415.  
  416. /* Return pointer to directory-less file name:                */
  417. char *BaseName(cc)
  418.  register char *cc;
  419.  {    register char *dd;
  420.     dd = cc;
  421.     for (;*cc;++cc) if ((*cc == '/') || (*cc == '\\')) dd = cc+1;
  422.     return dd;
  423.  }
  424.  
  425. char *extension(name)
  426.  char *name;
  427.  {    while (*name && (*name != '.')) name++;
  428.     return name;
  429.  }
  430.  
  431. main(argc, argv)
  432.  char **argv;
  433.  {    char *arg, argn, tobsq = 0;
  434.  
  435.     while ((argc>1) && (*(arg=argv[1]) == '-'))    /* OPTIONS    */
  436.       switch (*++arg)
  437.         {
  438.             case 'o':    OldFlag = 1; argv++; argc--;
  439.                     Partials = 0;
  440.                     continue;
  441.             case 'b':    BFlag = 1; argv++; argc--; continue;
  442.             default:    Error("Illegal option '%s'", argv[1]);
  443.         }
  444.  
  445.     if ((argc < 2) || (argc > 3)) Usage();
  446.     from = argv[1];
  447.  
  448.  
  449.     if (!strcmp(extension(from), ".bsq"))
  450.      { if (argc > 2) strcpy(to, argv[2]);
  451.        tobsq = 0;
  452.      }
  453.     else
  454.      { if (argc > 2) strcpy(to, argv[2]);
  455.        else { strcpy(to, BaseName(from));
  456.           strcpy(extension(to), ".bsq");
  457.         }
  458.        tobsq = 1;
  459.      }
  460.  
  461.     NodeInit();
  462.  
  463.     /* Open input and output files.                    *
  464.      * NB: Files must be read/written in BINARY.  If your C        *
  465.      * environment (eg Lattice MSDOS) requires some funny code to    *
  466.      * open files for binary I/O, do it here!            */
  467.  
  468.     if (!(in = fopen(from, "r"))) Error("Can't read file %s", from);
  469.     if (!tobsq) RdHeader();
  470.  
  471.     if (!(out = fopen(to, "w"))) Error("Can't write file %s", to);
  472.  
  473.     Msg("W1GOH Binary SQueeze 2.0: %s -> %s\r\n", from, to);
  474.     if (tobsq) Squeeze();
  475.     else UnSqueeze();
  476.     return 0;
  477.  }
  478.  
  479.  
  480. Usage()
  481.  {    Error("Usage: bsq infile [outfile]\r\n");
  482.  }
  483.  
  484. /************************************************************************
  485.  *                                    *
  486.  * Actual conversion happens here.                    *
  487.  *                                    *
  488.  * Algorithm:                                *
  489.  *   bytes 041 - 0xx are 6-bit data, bit-stuffed into output byte stream*
  490.  *   Each 8-bit output byte shifted into LastCh output fifo, whence    *
  491.  *    LastCh[0] is most recent byte, LastCh[1] next most recent, etc    *
  492.  *   Remaining 30 codes are META bytes, and cause output from defn    *
  493.  *    (besides flushing any accumulated partial byte if !Partials)    *
  494.  ************************************************************************/
  495.  
  496. /* File conversion: BINARY -> ASCII                    */
  497.  
  498. Squeeze()
  499.  {    register ch, i;
  500.  
  501.     /* First, make space for a header:                */
  502.     WrHeader();
  503.     crlf();
  504.  
  505.     NBytes = Length = 0;
  506.     AscInit();
  507.  
  508.     for (;;)
  509.      {
  510.        if (!BFlag && (BinN < (BBSIZE-3)))
  511.         {    int rsize=0, rcnt, asize=0;
  512.  
  513.            if ((ch = Repeat()) && (FindSize > 1) && (ch > 4))
  514.             { rsize = ch;
  515.               rcnt = FindSize;
  516.             }
  517.  
  518.            asize = Abbrev();
  519.  
  520.            if ((rsize-1) > asize)    /* Use the repeat??    */
  521.             { if (!Partials)
  522.                FlushStuff();        /* Flush stuff state.    */
  523.               OutBin(METARPT-ASCBAS);    /* Use a meta char.    */
  524.               OutBin(rcnt);        /* Repeat count.    */
  525.               for (i=0; i<rsize; i++)
  526.             { checksum += Peek(i);
  527.             }
  528.               Remove(rsize);        /* Flush input string.    */
  529.               NBytes += rsize;
  530.               continue;
  531.             }
  532.  
  533.            if (asize)            /* Else, use abbrev?    */
  534.             { if (!Partials)
  535.                 FlushStuff();        /* Flush stuff state.    */
  536.               OutBin(FindBest+64);    /* Use a meta char.    */
  537.               NodeOut(FindBest);    /* Now update machine    */
  538.               for (ch=0; ch<FindSize; ch++)
  539.             { checksum += Peek(ch);
  540.             }
  541.               Remove(FindSize);        /* Flush input string.    */
  542.               NBytes += FindSize;
  543.               continue;
  544.             }
  545.         }
  546.  
  547.        if (!Partials && BinN)        /* Compatibility = pain!*/
  548.         { register i;
  549.           for (i=0; i<BinN; i++) OutAscii(BinBuf[i]);
  550.           BinN = 0;
  551.         }
  552.  
  553.        ch = Peek(0);
  554.        Remove(1);
  555.        if (ch == -1) break;
  556.        StuffOut(ch);
  557.        NodeOut(MKATOM(ch));
  558.        checksum += ch;
  559.        ++NBytes;
  560.      }
  561.  
  562.     AscFin();
  563.  
  564.     /* Then back to patch up header.                */
  565.     fseek(out, 0L, 0);        /* rewind.            */
  566.     WrHeader();
  567.     fclose(out);
  568.     fclose(in);
  569.     return 0;
  570.  }
  571.  
  572. /* Read header of .BSQ input file.
  573.  * If file name in *to has not been set, it is formatted from the
  574.  *   name specified in the header (stripping off directories).
  575.  */
  576.  
  577. unsigned    icheck;            /* Input checksum from header    */
  578. unsigned    iversion;        /* Input version number from hdr*/
  579. unsigned    ipartn;            /* Part number             */
  580. unsigned    inparts;        /* Total number of parts    */
  581.  
  582. RdHeader()
  583.  {    register i, j;
  584.  
  585.     /* Try to read a new header:                    */
  586.     i = fscanf(in, "=== BSQ ver %3d %6ld bytes %6u (%2u %2u) %s\n",
  587.         &iversion, &Length, &icheck, &ipartn, &inparts, fname);
  588.  
  589.     if (i != 6)
  590.      { /* Try for an old header:                    */
  591.        fseek(in, 0L, 0);
  592.        i = fscanf(in, "=== BSQ %d FILE %6ld %6u %s\n",
  593.         &iversion, &Length, &icheck, fname);
  594.        if (i != 4) Error("Non-BSQ header format on file %s", from);
  595.      }
  596.  
  597.     if (iversion > VERSION)
  598.         Error("This is BSQ version %d, file used newer version %d!",
  599.                 VERSION, iversion);
  600.  
  601.     for (i=0; fname[i]; i++) if (fname[i] < ' ') fname[i] = 0;
  602.     if (!*to)            /* Use this as output file?    */
  603.        strcpy(to, BaseName(fname));
  604.  
  605.     /* Version-specific features:                    */
  606.     switch (iversion)
  607.      { case 1:    Partials = 0; CheckColumns = 0; break;
  608.      }
  609.  }
  610.  
  611. /* Write a header to output file:                    */
  612. WrHeader()
  613.  {
  614.     if (OldFlag)            /* Old version header?        */
  615.       fprintf(out, "=== BSQ %d FILE %6ld %6u %s",
  616.         1, NBytes, 0x7FFF & checksum, BaseName(from));
  617.     else
  618.       fprintf(out, "=== BSQ ver %3d %6ld bytes %6u (%2u %2u) %s",
  619.         VERSION, NBytes, 0x7FFF & checksum, ipartn, inparts,
  620.                 BaseName(from));
  621.  }
  622.  
  623.  
  624. #define    LINSIZ    200            /* Maximum line size.        */
  625. byte    InBuf[LINSIZ];            /* Input line buffer        */
  626. int    InPtr=0, InSize=0;        /* Number of chars in InBuf    */
  627. int    Suspect=0, LineNo = 1;        /* Number of suspicious line.    */
  628.  
  629.  
  630. GetC()                    /* Fetch an input character...    */
  631.  {    while (InPtr == InSize)        /* At end of buffer?        */
  632.         if (!GetLine()) return EOF;    /* On end-of-file.    */
  633.     return InBuf[InPtr++];
  634.  }
  635.  
  636. GetLine()                /* Fetch an input line.        */
  637.  {    register i, ch;            /* Returns zero iff EOF.    */
  638.     InSize = InPtr = 0;
  639.     while (InSize == 0)
  640.      { for (; InSize<LINSIZ; ) switch (ch = getc(in))
  641.         { case EOF:    return 0;
  642.           case '\n':    LineNo++;
  643.           default:    if (ch > ' ')
  644.                  { InBuf[InSize++] = ch; continue; }
  645.                 if (!InSize) continue;
  646.                 goto GotLine;
  647.         }
  648.      }
  649.  
  650. GotLine:   if (Suspect)
  651.         Msg("Suspicious text in file %s, line %d\r\n", from, Suspect);
  652.        if (CheckColumns && (InSize != CheckColumns))
  653.             Suspect = LineNo;
  654.        else Suspect = 0;
  655.     return InSize;
  656.  }
  657.  
  658. UnSqueeze()
  659.  {    register ch;
  660.     BinInit();
  661.  
  662.     for (;;)
  663.      { ch = GetC();
  664.        if (ch == EOF) break;
  665.        if (ch > ' ') BinOut(ch);
  666.      }
  667.  
  668.     BinFin();
  669.     fclose(in);
  670.     fclose(out);
  671.  
  672.     if (Length != NBytes) Error("File size: %s is %ld, %s was %ld",
  673.                     to, NBytes, fname, Length);
  674.     if ((icheck & 0x7FFF) != (checksum & 0x7FFF))
  675.         Error("Checksum error... %x %x\r\n", icheck,  checksum);
  676.  }
  677.  
  678. /************************************************************************
  679.  *                                    *
  680.  * ASCII -> BINARY conversion routines.                    *
  681.  *   AscInit() - prepare for output.                    *
  682.  *   StuffOut(byte) - Bit-stuff a byte of 8 bits.            *
  683.  *   AscFin() - flush buffers                        *
  684.  *                                    *
  685.  ************************************************************************/
  686.  
  687. unsigned outbuf;        /* Partial output bytes.        */
  688. unsigned bits;            /* number of bits in outbuf        */
  689. unsigned outcol;        /* output chars on current text line    */
  690. unsigned runch, run;        /* For run-length encoding.        */
  691.  
  692. AscInit()
  693.  {    checksum = outcol = outbuf = bits = 0;
  694.     runch = run = 0;
  695.  }
  696.  
  697.  
  698. /* Bit-stuff an 8-bit byte:                        */
  699. StuffOut(b)
  700.  unsigned b;
  701.  {    register ch;
  702.  
  703.     outbuf <<= 8;        /* Stuff in the new byte.        */
  704.     outbuf |= (b & ((1 << 8)-1));
  705.     bits += 8;        /* 8 more bits.                */
  706.  
  707.     /* Now add to output, ASCBITS bits/output char:            */
  708.     while (bits >= ASCBITS)
  709.      { ch = (outbuf >> (bits-ASCBITS)) & 0x3F;    /* 6 Bits.    */
  710.        bits -= ASCBITS;
  711.        OutAscii(ch);
  712.        if (BinN)
  713.         { register i;
  714.           for (i=0; i<BinN; i++) OutAscii(BinBuf[i]);
  715.           BinN = 0;
  716.         }
  717.      }
  718.  }
  719.  
  720. /* Flush the bit-stuffed output:                    */
  721. FlushStuff()
  722.  {    if (bits > 0)        /* Output any remaining bits.        */
  723.         OutAscii(0x3F & (outbuf<<(ASCBITS-bits)));
  724.     outbuf = bits = 0;
  725.     if (BinN)
  726.         { register i;
  727.           for (i=0; i<BinN; i++) OutAscii(BinBuf[i]);
  728.           BinN = 0;
  729.         }
  730.  }
  731.  
  732. /* Output a number, relocated to printable ASCII range            */
  733. OutAscii(b)
  734.  {    b += ASCBAS;
  735.     putc(b, out);
  736.     if (++outcol >= COLUMNS) crlf();
  737.  }
  738.  
  739. AscFin()
  740.  {    FlushStuff();
  741.     if (outcol > 0) crlf();
  742.  }
  743.  
  744.  
  745. /* Output a CR/LF:                            */
  746. crlf()
  747.  {    putc('\r', out);    putc('\n', out);
  748.     outcol = 0;
  749.  }
  750.  
  751. /************************************************************************
  752.  *                                    *
  753.  * BINARY -> ASCII conversion routines.                    *
  754.  *   BinInit() - prepare for output.                    *
  755.  *   BinOut(byte) - output a byte of s bits.                *
  756.  *   BinFin() - flush buffers & close.                    *
  757.  *                                    *
  758.  ************************************************************************/
  759.  
  760. BinInit()
  761.  {    checksum = outcol = outbuf = bits = 0;
  762.  }
  763.  
  764.  
  765. /* Convert another ASCII input character to binary...            */
  766.  
  767. BinOut(b)
  768.  unsigned b;
  769.  {    register i, ch;
  770.  
  771.     b &= 0177;
  772.     if (b <= ' ') return;        /* Ignore control chars.    */
  773.  
  774.     ch = (b - 041) & ((1 << ASCBITS) -1);    /* Extract ASCBITS    */
  775.  
  776.     if (b >= METABAS)
  777.      { if (!Partials) bits = 0;    /* Flush bit-stuff pipe.    */
  778.        if (b == METARPT)        /* Repeat character?        */
  779.         { if ((ch=GetC()) == EOF) return;
  780.           ch = 0x3F & (ch - 041);/* Repeat count.        */
  781.           while (ch--) BinExp(Previous);
  782.           return;
  783.         }
  784.        BinExp(b-METABAS);        /* Expand the output.        */
  785.        NodeOut(b-METABAS);        /* Run the state machine.    */
  786.      }
  787.     else
  788.      { BinOut1(ch);            /* Bit-stuff input.        */
  789.      }
  790.  }
  791.  
  792.  
  793. BinOut1(b)
  794.  unsigned b;
  795.  {    register ch;
  796.  
  797.     outbuf <<= ASCBITS;        /* Stuff in the new byte.    */
  798.     outbuf |= b;
  799.     bits += ASCBITS;
  800.  
  801.     /* Now add to output, 8 bits/output char:            */
  802.     while (bits >= 8)
  803.      { ch = ((outbuf >> (bits-8)) & 0xFF);
  804.        NodeOut(MKATOM(ch));        /* Recognise it as output    */
  805.        bits -= 8;
  806.        putc(ch, out);
  807.        ++NBytes;
  808.        checksum += ch;
  809.      }
  810.  }
  811.  
  812. /* Expand & output binary bytes for a node.                */
  813. BinExp(n)
  814.  NodeID n;
  815.  {    register j;
  816.  
  817.     if (n == UNUSED) return 0;
  818.     if (ATOMIC(n))
  819.      { j = DATA(n);
  820.        putc(j, out);
  821.        ++NBytes;
  822.        checksum += j;
  823.      }
  824.     else
  825.      { BinExp(Nodes[n].Left);
  826.        BinExp(Nodes[n].Right);
  827.      }
  828.  }
  829.  
  830.  
  831. BinFin()
  832.  {    if ((bits > 0) && (NBytes != Length))    /* Output any remaining bits.*/
  833.      { outbuf &= ((1 << bits)-1);
  834.        putc(outbuf, out);
  835.        checksum += outbuf;
  836.        NBytes++;
  837.      }
  838.  }
  839.  
  840. /************************************************************************
  841.  * Misc. utilitiy functions                        *
  842.  ************************************************************************/
  843.  
  844. Error(a0,a1,a2,a3,a4,a5)        /* Fatal error handler --    */
  845.  {    fprintf(stderr,            /* Called like printf.        */
  846.         a0,a1,a2,a3,a4,a5);
  847.     fprintf(stderr, "\r\n");
  848.     exit(-1);
  849.  }
  850.  
  851. Msg(a0,a1,a2,a3,a4,a5)            /* Message, for debugging.    */
  852.  {    fprintf(stderr,            /* Called like printf.        */
  853.         a0,a1,a2,a3,a4,a5);
  854.     fprintf(stderr, "\r\n");
  855.  }
  856.